這是什麼

Tree 的一種演算法，BFS 的精神是，找尋的順序是一層一層，每層節點都有搜尋過。

首先想像有一個樹長這樣子：

如果是 BFS，會這樣搜尋：

A -> B -> C -> D -> E -> F -> G -> H -> I -> J -> K -> L -> M

這邊是 Queue 大顯身手的場合，將要檢測的節點放入其中，每次檢查 Dequeue 的節點，如果沒找到將該節點的子節點放入 Queue 內。重複直到找到或是所有節點都已搜尋過。

刷題：101. Symmetric Tree

題目

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following [1,2,2,null,3,null,3] is not:

    1
   / \
  2   2
   \   \
   3    3

Follow up: Solve it both recursively and iteratively.

思考

參考 BFS 的做法，每層節點找尋完畢後，再挪到下一層找尋。
倒是可以先檢查 Binary Tree 節點數量，應該要是奇數個。（沒意義）

解題

JS

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
const isSymmetric = (root) => {
  // return whileLoopAnswer(root);
  return recursiveAnswer(root);
};

/**
 * @param {TreeNode} root
 */
const whileLoopAnswer = (root) => {
  if (root === null) {
    return true;
  }

  if (root.left === null && root.right === null) {
    return true;
  }

  let queue = [];
  queue.push([root.left, root.right]);

  while (queue.length > 0) {
    const firstPair = queue.shift();
    const left = firstPair[0];
    const right = firstPair[1];

    if (left === null && right === null) {
      continue;
    }

    if (left === null || right === null) {
      return false;
    }

    if (left.val !== right.val) {
      return false;
    }

    queue.push([left.left, right.right]);
    queue.push([left.right, right.left]);
  }

  return true;
};

/**
 * @param {TreeNode} root
 */
const recursiveAnswer = (root) => {
  if (root === null) {
    return true;
  }

  if (root.left === null && root.right === null) {
    return true;
  }

  return helper(root.left, root.right);
};

/**
 * @param {TreeNode} left
 * @param {TreeNode} right
 */
const helper = (left, right) => {
  if (left === null && right === null) {
    return true;
  }

  if (left === null || right === null) {
    return false;
  }

  if (left.val !== right.val) {
    return false;
  }

  return helper(left.left, right.right) && helper(left.right, right.left);
};

Java

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return whileLoopAnswer(root);
        return recursiveAnswer(root);
    }

    public boolean whileLoopAnswer(TreeNode root) {
        if (root == null) {
            return true;
        }

        if (root.left == null && root.right == null) {
            return true;
        }

        Queue<TreeNode> queue1 = new LinkedList<>();
        Queue<TreeNode> queue2 = new LinkedList<>();

        queue1.add(root.left);
        queue2.add((root.right));

        while (!queue1.isEmpty()) {
            TreeNode node1 = queue1.poll();
            TreeNode node2 = queue2.poll();

            if (node1 == null && node2 == null) {
                continue;
            }

            if (node1 == null || node2 ==null) {
                return false;
            }

            if (node1.val != node2.val) {
                return false;
            }

            queue1.add(node1.left);
            queue2.add(node2.right);
            queue1.add(node1.right);
            queue2.add(node2.left);
        }

        return true;
    }

    public boolean recursiveAnswer(TreeNode root) {
        if (root == null) {
            return true;
        }

        if (root.left == null && root.right == null) {
            return true;
        }

        return helper(root.left, root.right);
    }

    public boolean helper(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        }

        if (left == null || right == null) {
            return false;
        }

        if (left.val != right.val) {
            return false;
        }

        return helper(left.left, right.right) && helper(left.right, right.left);
    }
}

C

bool helper(struct TreeNode *left, struct TreeNode *right)
{
    if (left == NULL && right == NULL)
    {
        return true;
    }

    if (left == NULL || right == NULL)
    {
        return false;
    }

    if (left->val != right->val)
    {
        return false;
    }

    return helper(left->left, right->right) && helper(left->right, right->left);
}

bool isSymmetric(struct TreeNode *root)
{
    if (root == NULL)
    {
        return true;
    }

    if (root->left == NULL && root->right == NULL)
    {
        return true;
    }

    return helper(root->left, root->right);
}

看法

寫到一半發現，BFS 很像在做 Linear Search，兩者都是一個一個有順序地遍歷每個節點。

另外，JS 實在是太好用，.push([a, b]) 不能再 Java 內重現，反倒要用兩個 Linked List 來處理。

最後寫 C 的時候，覺得動態陣列太難，很難用 while 實作出，想著想著，忽然想到可以用遞迴（Recursive）處理。寫完後發現太簡潔，於是 JS & Java 都另外寫遞迴的版本。

結論

BFS 是接觸 Graph 一定會學習的演算法，倒是出乎我意料的好理解。
期待明天的 DFS。

隔天學習 DFS 時，赫然發現遞迴的寫法其實是 DFS...
想想也對，DFS 的本質就是先找到分支的 Leaf，然後再往回推，這理念跟遞迴相似...